package leetcode;

import java.util.Scanner;

public class JumpGame {

	public static void main(String[] args) {
//		Scanner scanner = new Scanner(System.in);
//		int number;
//		int[] nums;
//		while (scanner.hasNext()) {
//			number = scanner.nextInt();
//			nums = new int[number];
//			for (int i = 0; i < nums.length; i++) {
//				nums[i] = scanner.nextInt();
//			}
//			canJump2_2(nums);
//		}
//		scanner.close();
		int[] A = {0};
		int[] B = {2,1,3,1,4};
		System.out.println(canJumpMy(A));
		canJump2_2(B);
	}

	// if it can jump
	public static boolean canJumpMy(int[] A) {
		if (A == null || A.length <= 0) {
			return true;
		}
		int max = 0;
		for (int i = 0; i < A.length - 1; i++) {
			// 如果第i个石头可达
			if (max >= i) {
				//Unbelievable, when I use max function, TLE in the leeftcode
				max = Math.max(max, A[i] + i);
			}
		}
		return max >= A.length - 1;
	}

	// 判断是否可以到达对岸
	public static boolean canJump1(int[] A) {
		if (A == null || A.length <= 0) {
			return true;
		}
		int max = 0; // 标记能够跳的最远点
		// max >= i 表示能够到达i
		for (int i = 0; i < A.length && max >= i; i++) {
			// i + A[i] 表示从i处能够到达的最远点
			if (i + A[i] > max) {
				max = A[i] + i;
			}
		}
		return max >= A.length - 1;
	}

	// 判断最少需要跳的次数
	public static void canJump2_1(int[] A) {
		int stepCount = 0;  //the minimum step
		int last_jump_max = 0;  // longest distance in current minimum step
		int max = 0;
		for (int i = 0; i < A.length - 1; i++) {
			max = Math.max(max, i + A[i]);
			if (i == last_jump_max ) {
				stepCount++;
				last_jump_max  = max;
			}
		}
		if (max >= A.length - 1) {
			System.out.println(stepCount);
		} else {
			System.out.println(-1);
		}
	}

	// 判断最少需要跳的步数
	public static void canJump2_2(int[] A) {
		if (!canJump1(A)) {
			System.out.println(-1);
		}
		int cur = 0; // 每个石头内最远去的地方
		int last = 0; // 上一次跳跃到的最远的位置
		int step = 0; // 跳的次数
		for (int i = 0; i < A.length && cur >= i; ++i) {
			if (i > last) {
				System.out.println("i :" + i + " last : " + last);
				last = cur;
				step++;
			}
			cur = Math.max(cur, A[i] + i);
		}
		System.out.println(step);
	}
}
